/**
 * 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 * <p>
 * ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。
 * <p>
 * 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [2,5,6,0,0,1,2], target = 0
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: nums = [2,5,6,0,0,1,2], target = 3
 * 输出: false
 * 进阶:
 * <p>
 * 这是 搜索旋转排序数组 的延伸题目，本题中的 nums  可能包含重复元素。
 * 这会影响到程序的时间复杂度吗？会有怎样的影响，为什么？
 */
class Solution {

    public static void main(String[] args) {
        System.out.println(search(new int[]{2, 5, 6, 0, 0, 1, 2}, 1));
        System.out.println(search(new int[]{1, 3, 1, 1}, 3));
        System.out.println(search(new int[]{1, 1, 3}, 3));
        System.out.println(search(new int[]{1, 2, 2, 2, 0, 1, 1}, 0));
        System.out.println(search(new int[]{10, 10, 10, -10, -10, -10, -10, -9, -9, -9, -9, -9, -9, -9, -8, -8, -8, -8, -8, -8, -8, -8, -7, -7, -7, -7, -6, -6, -6, -5, -5, -5, -4, -4, -4, -4, -3, -3, -2, -2, -2, -2, -2, -2, -2, -2, -1, -1, -1, -1, -1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 10, 10}, -6));
    }

    public static boolean search(int[] nums, int target) {
        if (nums.length == 0) {
            return false;
        }
        int head = nums[0];
        int mid = nums.length / 2;
        if (target == head) {
            return true;
        } else if (target > head) {
            // 如果目标大于头，则在头和旋转点之间找到
            for (int x = 0, y = nums.length; x < y - 1; ) {
                if (target == nums[mid]) {
                    return true;
                } else if (target < nums[mid] || nums[mid] < head) {
                    // 往小了找
                    y = mid;
                    mid = (x + mid) / 2;
                } else if (nums[mid] == head) {
                    // 从head到mid有比head大的，则往小了找。否则表示从head到mid都是一样的，往大了找
                    boolean goBig = true;
                    for (int i = x + 1; i < mid; i++) {
                        if (nums[i] > head) {
                            goBig = false;
                            break;
                        }
                    }
                    if (goBig) {
                        // 往大了找
                        x = mid;
                        mid = (y + mid) / 2;
                    } else {
                        // 往小了找
                        y = mid;
                        mid = (x + mid) / 2;
                    }
                } else {
                    // 往大了找
                    x = mid;
                    mid = (y + mid) / 2;
                }
            }
        } else {
            // 如果目标小于头，则在旋转点和尾之间找到
            for (int x = 0, y = nums.length; x < y - 1; ) {
                if (target == nums[mid]) {
                    return true;
                } else if (target > nums[mid] || nums[mid] > head) {
                    // 往大了找
                    x = mid;
                    mid = (y + mid) / 2;
                } else if (nums[mid] == head) {
                    // 从mid到end有比mid大的
                    boolean goSmall = true;
                    for (int i = mid; i < nums.length; i++) {
                        if (nums[i] < head) {
                            goSmall = false;
                            break;
                        }
                    }
                    if (goSmall) {
                        // 往小了找
                        y = mid;
                        mid = (x + mid) / 2;
                    } else {
                        // 往大了找
                        x = mid;
                        mid = (y + mid) / 2;
                    }
                } else {
                    // 往小了找
                    y = mid;
                    mid = (x + mid) / 2;
                }
            }
        }
        return false;
    }
}